import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Random;

class KthLargest {

    public static int k;
    /**
     * 前面类中对heap进行初始化，会导致多次测试案例共用一个堆，进而数据错误
     * 故对于此类设计类的题型，我们应当尽量避免全局变量直接初始化从而导致的测试数据重复问题*/
    public static PriorityQueue<Integer> heap;

    public KthLargest(int _k, int[] nums) {
        /**
         * 初始化*/
        KthLargest.k = _k;
        heap = new PriorityQueue<>();
        // -初始化小根堆
        for(int e: nums) {
            heap.offer(e);
            // -堆中元素恰好为k（堆中维护最大k个元素，堆顶为其中最小值，若是枚举元素大于对顶元素，则出队堆顶入新元素）
            if(heap.size() > k) {
                heap.poll();
            }
        }
    }

    public int add(int val) {
        /**
         * 维护topk*/
        heap.offer(val);
        if(heap.size() > k) {
            heap.poll();
        }
        return heap.peek();
    }

    public static int[] nums = new int[20000];
    public static int len;

//    public KthLargest(int k, int[] nums) {
//        /**
//         * 初始化设计类*/
//        KthLargest.k = k;
//        KthLargest.len = nums.length;
//        for(int i = 0; i < KthLargest.len; i++) {
//            KthLargest.nums[i] = nums[i];
//        }
//    }
//
//    public int add(int val) {
//        /**
//         * 插入数据并返回数据流中第k大元素
//         * 本算法缺陷在于，每次都会对数据进行排序，等下看看老师有什么巧妙的思路*/
//        // 1 插入
//        KthLargest.nums[KthLargest.len++] = val;
//        return quickSelect(KthLargest.k, 0, KthLargest.len-1);
//    }

    private int quickSelect(int k, int left, int right) {
        /**
         * 快速选择算法解决Topk问题
         * 找到第k大元素*/
        // 1 递归出口
        if(left == right) {
            return KthLargest.nums[left];
        }

        // 2 三路快排
        int key = KthLargest.nums[left + new Random().nextInt(right - left + 1)];
        // -数组分三块
        int l = left -1;
        int r = right + 1;
        int i = left;
        while(i < r) {
            if(KthLargest.nums[i] < key) {
                swap(++l, i++);
            } else if(KthLargest.nums[i] == key) {
                i++;
            } else {
                swap(--r, i);
            }
        }

        // 3 根据k所在区间进行递归
        int b = right - l;
        int c = right - r + 1;
        if(k <= c) {
            return quickSelect(k, r, right);
        } else if(k <= b) {
            return key;
        } else {
            return quickSelect(k-b, left, l);
        }
    }

    private void swap(int i, int j) {
        /**
         * 交换i j下标元素*/
        int temp = KthLargest.nums[i];
        KthLargest.nums[i] = KthLargest.nums[j];
        KthLargest.nums[j] = temp;
    }
}
